#include <stdio.h>
#include <stdlib.h>

typedef struct PolyNode *Polynomial;
struct PolyNode {
    int coef;
    int expon;
    Polynomial link;
};


void Attach(int c, int e, Polynomial *pRear);

Polynomial ReadPoly();

Polynomial Add(Polynomial P1, Polynomial P2);

Polynomial Mul(Polynomial P1, Polynomial P2);

void PrintPoly(Polynomial P);


int main() {
    Polynomial P1, P2, PP, PS;
    P1 = ReadPoly();
    P2 = ReadPoly();
    PP = Mul(P1, P2);
    PrintPoly(PP);
    PS = Add(P1, P2);
    PrintPoly(PS);
    return 0;
}

void Attach(int c, int e, Polynomial *pRear) {
    Polynomial temp;
    temp = (Polynomial) malloc(sizeof(struct PolyNode));
    temp->coef = c;
    temp->expon = e;
    temp->link = NULL;
    (*pRear)->link = temp;
    *pRear = temp;
}

Polynomial ReadPoly() {
    Polynomial P, Rear, first;
    int N, c, e;

    P = (Polynomial) malloc(sizeof(struct PolyNode)); // 头结点
    P->link = NULL;
    Rear = P;
    scanf("%d", &N);

    while (N--) {
        scanf("%d %d", &c, &e);
        Attach(c, e, &Rear);
    }

    first = P; // 删除临时头结点
    P = P->link;
    free(first);
    return P;
}

Polynomial Add(Polynomial P1, Polynomial P2) {
    Polynomial t1, t2, P, Rear, t;
    int c, e;
    if (!P1 && !P2) return NULL;
    t1 = P1;
    t2 = P2;

    P = (Polynomial) malloc(sizeof(struct PolyNode));
    Rear = P;
    while (t1 && t2) {
        if (t1->expon == t2->expon) {
            if (t1->coef != -(t2->coef)) Attach(t1->coef + t2->coef, t1->expon, &Rear);
            t1 = t1->link;
            t2 = t2->link;
        } else if (t1->expon > t2->expon) {
            Attach(t1->coef, t1->expon, &Rear);
            t1 = t1->link;
        } else {
            Attach(t2->coef, t2->expon, &Rear);
            t2 = t2->link;
        }
    }
    Rear->link = t1 ? t1 : t2;
    t = P;
    P = P->link;
    free(t);
    return P;
}

// 逐项插入
Polynomial Mul(Polynomial P1, Polynomial P2) {
    Polynomial t1, t2, P, Rear, t;
    int c, e;
    // 两个多项式相乘，只要有一个为空，结果就为空
    if (!P1 || !P2) return NULL;
    t1 = P1;
    t2 = P2;
    P = (Polynomial) malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P;
    while (t2) {
        // 对第二个多项式进行处理,第一个多项式的第一项乘第二个多项式的每一项
        Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
        t2 = t2->link;
    }
    t1 = t1->link;
    while (t1) {
        Rear = P;
        t2 = P2;
        while (t2) {
            c = t1->coef * t2->coef;
            e = t1->expon + t2->expon;
            // 问题转化为以知指数和系数，插入一个降指数排列的多项式
            // 当下一项的指数比要插入的大，指针向后移动
            while (Rear->link && Rear->link->expon > e) Rear = Rear->link;
            // 如果指数相等
            if (Rear->link && Rear->link->expon == e) {
                // 如果系数相加不等于0
                if (Rear->link->coef + c) Rear->link->coef += c;
                    // 系数相加等于0，删除此结点
                else {
                    t = Rear->link;
                    Rear->link = t->link;
                    free(t);
                }
            } // 如果指数不相等，创建新结点，插入
            else {
                t = (Polynomial) malloc(sizeof(struct PolyNode));
                t->coef = c;
                t->expon = e;
                t->link = Rear->link;
                Rear->link = t;
                Rear = Rear->link;
            }
            t2 = t2->link;
        }
        t1 = t1->link;
    }
    t = P;
    P = P->link;
    free(t);
    return P;
}

//把链表以数字的形式输出
void PrintPoly(Polynomial P) {
    if (!P) {  // P==NULL时, !P为真
        printf("0 0");
    }
    while (P) { // 相当于P!=NULL
        printf("%d %d", P->coef, P->expon);
        P = P->link;
        if (P != NULL) {
            //只有在指针域不为NULL时，才输出空格间隔开每个多项式。即在多项式末位没有空格
            printf(" ");
        }
    }
    printf("\n");
}